package Solution125_150;

import org.junit.Test;

import java.util.List;

public class Solution134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {

        for(int i=0;i<gas.length;i++){
            if(check(i,gas,cost)){
                return i;
            }
        }
        return -1;
    }

    private boolean check(int startIndex,int[] gas,int[] cost){
        int sum=gas[startIndex];
        for(int i=startIndex+1;;i++){
            sum-=cost[(i-1)%cost.length];
            if(sum<0){
                return false;
            }
            if(i%gas.length==startIndex){
                return true;
            }
            sum+=gas[i%gas.length];
        }
    }


    public int betterCanCompleteCircuit(int[] gas, int[] cost) {
        /**
         * gas总量大于cost总量时一定存在某个站点能够开完全程
         * */
        int n = gas.length;
        int total_tank = 0;
        int curr_tank = 0;
        int starting_station = 0;
        for (int i = 0; i < n; ++i) {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];
            if (curr_tank < 0) {//说明断油了
                starting_station = i + 1;
                curr_tank = 0;
            }
        }
        return total_tank >= 0 ? starting_station : -1;
    }

    @Test
    public void test(){
       int[] gas=new int[]{3,3,4};
       int[] cost=new int[]{3,4,4};
        /**
         * [3,3,4]
         * [3,4,4]
         */
       int result=canCompleteCircuit(gas,cost);
        System.out.println(result);
    }

}
